import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ghp
 * @date 2023/6/9
 * @title
 * @description
 */
class Solution {
    public int trap(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 当前柱子比上一个柱子要高，说明出现了右边界
                // 则计算当前右边界与 最开始入栈的那个柱子（也就是左边界，栈是递减的） 构成的容器能容纳的雨水
                int h = height[stack.pop()]; // 出栈得到当前准备接纳雨水的柱子高度
                if (stack.isEmpty()) {
                    // 如果此时栈为空，则说明只剩最后两个柱子了（一个左边界，一个右边界）
                    // 无法构成接纳雨水的容器，直接退出循环
                    break;
                }
                // 计算左右边界之间的距离
                int distance = i - stack.peek() - 1;
                // 获取左右边界中较短的高度
                int min = Math.min(height[stack.peek()], height[i]);
                // 将当前柱子接纳的雨水加入 ans 中
                ans += distance * (min - h);
            }
            stack.push(i);
        }
        return ans;
    }
}